This invention relates to data multiplexing, that is, to forming a single composite data stream from a plurality of constituent data streams for sending over a transmission link, and to the recovery of the separate constituent streams on the other end of the link.
A typical situation employing multiplexing might be that of a bank branch where each of several tellers has his terminal and sends and receives information over a single telephone circuit connected to a terminal at the bank's central accounting facility. In such an arrangement the generation of data at or for any particular terminal may vary from instant to instant and its need for link capacity will correspondingly vary. In general the information capacity of the link will be greater than that of any single terminal but may not be greater than the aggregate of all terminals. Since in many systems the cost of the transmission link is expensive, it is important to multiplex efficiently taking account of the varying demand from the several terminals to achieve maximum benefit from the link's transmission capacity. It is also important to maintain the delay through the system at an acceptably short time.
The invention features in one aspect a multiplexer having therein a plurality of queues, each associated with one of several constituent data streams and arranged and connected to receive and store data therefrom, protocol-defining apparatus defining a service sequence for the queues, each queue appearing at least once in the sequence, and a codeword set, the elements thereof being bit sequences of non-uniform length, the set being uniquely parsable and including a terminator codeword used to designate the end of a slot, and framing means, communicating with the protocol-defining apparatus, and arranged and connected to emit a bit stream in a sequence of time slots corresponding to the defined service sequence, the data in any one slot being derived from its associated queue, and in the form of codewords from the codeword set, the framing apparatus emitting terminator codewords to mark the end of at least some slots.
In another aspect the invention features in a demultiplexer protocol-defining apparatus defining a service sequence for a plurality of constituent data streams, each constituent stream appearing at least once in the sequence, and a codeword set, the elements thereof being bit sequences of non-uniform length, the set being uniquely parsable and including a terminator codeword used to designate the end of a slot, parsing means, communicating with said protocol-defining apparatus, arranged and connected to parse and decode a composite stream of bits received from a transmission link in a sequence of time slots corresponding to said defined service sequence, the data in any one slot being derived from its associated constituent stream, and being in the form of codewords from said codeword set, and having terminator codewords marking the ends of at least some slots.
The invention additionally features in particular embodiments a single codeword set encoding together data characters and terminal control signal information from the constituent streams; a codeword set chosen to reflect the statistics of data frequency, with shorter codewords assigned to more frequent data; framing apparatus emitting in each successive slot all the data then stored in the associated queue plus a terminator codeword as the final codeword of each slot; protocol-defining apparatus additionally defining for each member of the service sequence a maximum codeword count and framing apparatus placing in each successive slot codewords corresponding to all the data then stored in the associated queue when the data then stored is less than that defined by the associated maximum codeword count followed by a terminator codeword, and otherwise an amount of data as defined by the maximum codeword count; a terminator codeword having a length of at least two bits; assignment of a maximum codeword count greater than 1 for at least one member of said service sequence.
A multiplexing system according to the invention achieves a high utilization of the link capacity together with short delay and flexibility in making the link capacity available to the terminals in response to their varying demands for service. It does this by defining a cyclical order of service for the terminals, the order being known at both the multiplexer and the demultiplexer. Both the multiplexer and the demultiplexer keep a record of the current status of the cycle, the receiver updating this record by reference to the incoming data. The demultiplexer can thus direct received data to the proper destination terminal by reference to the defined order together with the record of current status without requiring transmission of any identifying address. While the terminal service order is fixed, the amount of service to the several terminals, that is the amount of data sent, is permitted to vary in response to the changing demand at each terminal so that more of the link capacity is used to serve the more active terminals. Transitions in service from one terminal to the next in the cycle are indicated by transmission of a distinct terminator codeword. Alternatively, a maximum service during a service cycle for each terminal can be defined and the distinct terminator codeword transmitted only when (because of insufficient demand by the particular terminal) a transition is made after a lesser amount of service has been given.